// 搜索二叉树
class Node{
  constructor(key, left = null, right = null){
    super();
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

function predesccessor (root) {
  let temp = root.left;
  while(temp.right) temp = temp.right;
  return temp;
}

Node.prototype.getNewNode = function(key){
  return new Node(key);
}

Node.prototype.insert = function(root, key){
  if(!root) return this.getNewNode();
  if(root.key === key) return root;
  if(key < root.key) root.left = this.insert(root.left, key);
  else root.right = this.insert(root.right, key);
  return root;
}

Node.prototype.erase = function(root, key){
  if(!root) return root;
  if(key < root.key){
    root.left = this.erase(root.left, key);
  } else if(key > root.key){
    root.right = this.erase(root.right, key);
  } else {
    // 度为0
    if(!root.left && !root.right){
      delete root;
      return null;
    } else if(!root.left || !root.right) {
      // 度为1
      const temp = root.left ? root.left : root.right;
      delete root;
      // 返回删除节点的子节点
      return temp;
    } else {
      // 度为2
      // 查找前驱节点
      const temp = predesccessor(root);
      // 替换为前去节点的值
      root.key = temp.key;
      // 从root.left中，删除前驱节点。 转为了删除度为1的
      root.left = this.erase(root.left, temp.key);
    }
  }
  return root;
}